/*!
 * \file heurPartiteSubgraph.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Heuristics for coloring, maximum stable set and maximum clique.
 */

#include <stdlib.h>
#include <bitmap.h>
#include <graph.h>
#include <heurPartiteSubgraph.h>

static NODETYPE * RR; //!< Auxiliary bitmap used in various heuristics.
static Graph * heurg; //!< Input graph of the heuristics.
static size_t memsz = 0; //!< Memory space used by the heuristics.

// mcsColoring
static int * nextInColor = NULL; //!< Vertices classified by colors

// fracColoring
static NODETYPE * E = NULL; //!< Auxiliary bitmap used in \c fracColoring.
static NODETYPE * EE; //!< Auxiliary bitmap used in \c fracColoring.
static NODETYPE * S; //!< Auxiliary bitmap used in \c fracColoring.

void initHeur(Graph * g) {
	heurg = g;
	int nnodes = NODEIDX(g->n-1) + 1;

#ifdef _SSE_
	RR = (NODETYPE *) aligned_malloc((nnodes+3) * WSIZE);
#else
	RR = (NODETYPE *) calloc(nnodes, WSIZE);
#endif

	memsz += (nnodes << LOGW);
	nextInColor = NULL;
}

void closeHeur() {
#ifdef _SSE_
	aligned_free(RR);
#else
	free(RR);
#endif

	RR = NULL;
	heurg = NULL;

	if (nextInColor != NULL) {
		free(nextInColor);
		nextInColor = NULL;
	}

	if (E != NULL) {
		free(E);
		E = NULL;
		EE = NULL;
	}
}

size_t getMemSize() {
	return memsz;
}

/*!
 * \fn int greedyColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
int greedyColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode) {
	int size = 0;
	int vidx = 0;
	int nodeidx;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;

	while (size < lim && *minRNode <= *maxRNode) {
		nodeidx = *minRNode;
		copyAll(RR, R, nodeidx, *maxRNode + 1);
		if (nodeidx < *minWNode)
			*minWNode = nodeidx;
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
		while (vidx >= 0) {
			removeAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, *maxRNode + 1);
			*nodeRR = DELFROMNODE(*nodeRR, vidx);
			nodeR = (R + nodeidx);
			*nodeR = DELFROMNODE(*nodeR, vidx);
			nodeW = (W + nodeidx);
			*nodeW = ADDTONODE(*nodeW, vidx);
			lastnodeidx = nodeidx;
			nodeidx = minNode(RR, nodeidx, *maxRNode);
			nodeRR = (RR + nodeidx);
			vidx = NODELEAST(*nodeRR);
		}
		if (lastnodeidx > *maxWNode)
			*maxWNode = lastnodeidx;
		*minRNode = minNode(R, *minRNode, *maxRNode);
		*maxRNode = maxNode(R, *maxRNode, *minRNode);

		size++;
	}

	return size;
}

/*!
 * \fn int maxClique(NODETYPE * R, int minRNode, int maxRNode)
 * \brief Greedy heuristic for maximum clique.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum clique.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 *
 * \return The size of the clique found.
 */
int maxClique(NODETYPE * R, int minRNode, int maxRNode) {
	int nodeidx = minRNode;
	copyAll(RR, R, nodeidx, maxRNode + 1);

	NODETYPE * nodeRR = (RR + nodeidx);
	int vidx = NODELEAST(*nodeRR);
	int size = 0;
	while (vidx >= 0) {
		size++;
		retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}

	return size;
}

/*!
 * \fn void maxStab(NODETYPE * R, NODETYPE * W, int u, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for maximum stable set containing a specified vertex.
 *
 * The vertices in the specified bitmap are greedily searched for a maximum stable set. The vertices in the stable set found are removed from
 * the input bitmap and stored in the output bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param u The vertex to expand to a stable set.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 */
void maxStab(NODETYPE * R, NODETYPE * W, int u, int * minRNode, int * maxRNode,
		int * minWNode, int * maxWNode) {
	int nodeidx = *minRNode;
	copyAll(RR, R, nodeidx, *maxRNode + 1);

	removeAll(RR, NEIG(heurg, u), nodeidx, *maxRNode + 1);
	nodeidx = minNode(RR, nodeidx, *maxRNode);

	int vidx = 0;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;

	nodeRR = (RR + nodeidx);
	if (!*nodeRR)
		return;

	vidx = NODELEAST(*nodeRR);
	while (vidx >= 0) {
		removeAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, *maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeR = (R + nodeidx);
		*nodeR = DELFROMNODE(*nodeR, vidx);
		nodeW = (W + nodeidx);
		*nodeW = ADDTONODE(*nodeW, vidx);
		lastnodeidx = nodeidx;
		nodeidx = minNode(RR, nodeidx, *maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}
	if (lastnodeidx > *maxWNode)
		*maxWNode = lastnodeidx;
	*minRNode = minNode(R, *minRNode, *maxRNode);
	*maxRNode = maxNode(R, *maxRNode, *minRNode);
}

/*!
 * \fn int expClique(NODETYPE * R, int * C, int minRNode, int maxRNode, int topC)
 * \brief Greedy heuristic for expanding a specified clique.
 *
 * The vertices in the specified bitmap are greedily searched to entering the specified clique.
 *
 * \param R Input bitmap of vertices to color.
 * \param C The input clique.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param topC Size of input clique.
 *
 * \return The size of the expanded clique.
 */
int expClique(NODETYPE * R, int * C, int minRNode, int maxRNode, int topC) {
	int nodeidx = minRNode;
	copyAll(RR, R, nodeidx, maxRNode + 1);

	int size = 0;

	int t = topC;
	while (--t >= 0 && nodeidx <= maxRNode) {
		retainAll(RR, NEIG(heurg, C[t]), nodeidx, maxRNode + 1);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		size++;
	}

	if (size < topC)
		return topC;

	NODETYPE * nodeRR = (RR + nodeidx);
	int vidx = NODELEAST(*nodeRR);
	while (vidx >= 0) {
		size++;
		retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), nodeidx, maxRNode + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeidx = minNode(RR, nodeidx, maxRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
	}

	return size;
}

int maxCliqueWith(NODETYPE * R, NODETYPE * W, int u, int minRNode, int maxRNode,
		int minWNode, int maxWNode) {
	int nodeidx = maxRNode;
	int minRRNode = minRNode;
	copyAll(RR, R, minRNode, nodeidx + 1);
	addAll(RR, W, minWNode, maxWNode + 1);
	if (maxWNode > nodeidx)
		nodeidx = maxWNode;
	if (minWNode < minRRNode)
		minRRNode = minWNode;

	int size = 0;

	retainAll(RR, NEIG(heurg, u), minRRNode, nodeidx + 1);
	nodeidx = maxNode(RR, nodeidx, minRRNode);
	size++;

	NODETYPE * nodeRR = (RR + nodeidx);
	int vidx = NODEMOST(*nodeRR);
	while (nodeidx > minRRNode && vidx >= 0) {
		size++;
		retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), minRRNode, nodeidx + 1);
		*nodeRR = DELFROMNODE(*nodeRR, vidx);
		nodeidx = maxNode(RR, nodeidx, minRRNode);
		nodeRR = (RR + nodeidx);
		vidx = NODEMOST(*nodeRR);
	}
	if (nodeidx == minRNode)
		while (*nodeRR != 0 && vidx >= 0) {
			size++;
			retainAll(RR, NEIG(heurg, NELEM(nodeidx)+vidx), minRRNode,
					nodeidx + 1);
			*nodeRR = DELFROMNODE(*nodeRR, vidx);
			vidx = NODEMOST(*nodeRR);
		}

	return size;
}

static void printStackColor(int size) {
	int p, a;
	printf("%d-coloring:\n", size);
	for (p = 0; p < size; p++) {
		printf("color %d:", p);
		a = nextInColor[heurg->n + p];
		while (a < heurg->n) {
			printf(" %d", a);
			a = nextInColor[a];
		}
		printf("\n");
	}
}

static int checkStackColor(NODETYPE * R, NODETYPE * W, int size, char * str) {
	int p, a, b, q = 0;
	for (p = 0; p < size; p++) {
		a = nextInColor[heurg->n + p];
		if (ISINSET(R, a) || !ISINSET(W, a)) {
			printf("%s  color=%d  size=%d  a=%d  ISINR=%ld  ISINW=%ld\n", str,
					p, size, a, ISINSET(R, a), ISINSET(W, a));
			q = 1;
		}
		while (a < heurg->n) {
			b = nextInColor[a];
			while (b < heurg->n) {
				if (ISINSET(NEIG(heurg, a), b)) {
					printf("%s  color=%d  a=%d  b=%d\n", str, p, a, b);
					q = 1;
				}
				b = nextInColor[b];
			}
			a = nextInColor[a];
		}
	}

	return q;
}

/*!
 * \fn void mcsRecolor(NODETYPE * R, NODETYPE * W, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode, int size)
 * \brief Greedy heuristic for recoloring vertices by color exchanges.
 *
 * For every vertex \c p in the input bitmap, attempt to find a vertex \c q in the \c cover array such that the number of neighbors \c r
 * of \c p in the color \c k1 of \c q is at most 1. If such \c q is found, there are two cases. If \c r \c = \c 0, then add \c p to color
 * \c k1, updating \c cover and \c idx arrays. If \c r \c = \c 1, then attempt to find a color \c k2 containing no neighbors
 * in color \c k2. If such color \c k2 is found, then move \c q to color \c k2 and add \c p to color \c k1, removing it from the
 * input bitmap.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 * \param size Number of colors.
 *
 * \return The number of colors used.
 */
//void mcsRecolor(NODETYPE * R, NODETYPE * W, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode, int size);
static void mcsRecolor(NODETYPE * R, NODETYPE * W, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode, int size) {
	int vidx, v = 0;
	int vnode;
	int lastnodeidx = -1;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;
	int sentinel = heurg->n << 1;

	int u = 0, prevu;
	copyAll(RR, R, *minRNode, *maxRNode + 1);
	vnode = *minRNode;
	nodeRR = (RR + vnode);
	vidx = NODELEAST(*nodeRR);
	while (vidx >= 0) {
		int ucolor = 0;
		while (ucolor < size - 1) {
			int curInColor = nextInColor[heurg->n + ucolor];
			int prevInColor = heurg->n + ucolor;
			int hasNeig = 0;
			v = NELEM(vnode) + vidx;
			while (hasNeig < 2 && curInColor < heurg->n) {
				if (HASEDGE(heurg, v, curInColor)) {
					hasNeig++;
					u = curInColor;
					prevu = prevInColor;
				}
				prevInColor = curInColor;
				curInColor = nextInColor[curInColor];
			}

			if (hasNeig < 2) {
				int w, wcolor = -1;
				if (hasNeig == 0) {
					w = v;
					wcolor = ucolor;
				} else {
					int cl = ucolor + 1;
					while (cl < size) {
						int cc = nextInColor[heurg->n + cl];
						while (cc < sentinel && !HASEDGE(heurg,u,cc))
							cc = nextInColor[cc];
						if (cc == sentinel) {
							w = u;
							wcolor = cl;
							nextInColor[prevu] = nextInColor[u];
							nextInColor[v] = nextInColor[heurg->n + ucolor];
							nextInColor[heurg->n + ucolor] = v;
							cl = size;
						} else
							cl++;
					}
				}

				if (wcolor >= 0) {
					nextInColor[w] = nextInColor[heurg->n + wcolor];
					nextInColor[heurg->n + wcolor] = w;
					*nodeRR = DELFROMNODE(*nodeRR, vidx);
					*(R + vnode) = DELFROMNODE(*(R + vnode), vidx);
					nodeW = (W + vnode);
					*nodeW = ADDTONODE(*nodeW, vidx);
					if (vnode < *minWNode)
						*minWNode = vnode;
					lastnodeidx = vnode;
					ucolor = size;
					vidx = -1;

//					if (checkStackColor(R, W, size, "mcsRecolor v")) {
//						printf("v=%d  u=%d  w=%d\n",v,u,w);
//						printStackColor(size);
//						exit(0);
//					}
				}
			}
			ucolor++;
		}

		if (vidx >= 0)
			retainAll(RR, NEIG(heurg, v), vnode, *maxRNode + 1);
		else
			vidx = NODEIDX(v);
		if (*nodeRR)
			vidx = NODENEXTLEAST(*nodeRR, vidx);
		else
			vidx = -1;
		while (vidx < 0 && vnode < *maxRNode) {
			nodeRR = (RR + (++vnode));
			vidx = NODELEAST(*nodeRR);
		}
	}

	if (lastnodeidx >= 0) {
		if (lastnodeidx > *maxWNode)
			*maxWNode = lastnodeidx;
		*minRNode = minNode(R, *minRNode, *maxRNode);
		*maxRNode = maxNode(R, *maxRNode, *minRNode);
	}

//	checkStackColor(R, W, size, "mcsRecolor");
}

/*!
 * \fn int stackColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for vertex coloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 * The colors created are represented in \c cover and \c idx arrays.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
//int stackColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode);
static int stackColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode) {
	int size = 0;
	int vidx = 0;
	int nodeidx;
	int lastnodeidx = 0;
	NODETYPE * nodeR;
	NODETYPE * nodeRR;
	NODETYPE * nodeW;
	int sentinel = heurg->n << 1;

	if (nextInColor == NULL) {
		nextInColor = (int *) calloc((heurg->n + 1) << 1, sizeof(int));
		memsz += (((heurg->n + 1) * sizeof(int)) << 1);
	}

	nextInColor[heurg->n] = sentinel;

	while (size < lim && *minRNode <= *maxRNode) {
		nodeidx = *minRNode;
		copyAll(RR, R, nodeidx, *maxRNode + 1);
		if (nodeidx < *minWNode)
			*minWNode = nodeidx;
		nodeRR = (RR + nodeidx);
		vidx = NODELEAST(*nodeRR);
		while (vidx >= 0) {
			int v = NELEM(nodeidx) + vidx;
			removeAll(RR, NEIG(heurg, v), nodeidx, *maxRNode + 1);
			*nodeRR = DELFROMNODE(*nodeRR, vidx);
			nodeR = (R + nodeidx);
			*nodeR = DELFROMNODE(*nodeR, vidx);
			nodeW = (W + nodeidx);
			*nodeW = ADDTONODE(*nodeW, vidx);

			nextInColor[v] = nextInColor[heurg->n + size];
			nextInColor[heurg->n + size] = v;

			lastnodeidx = nodeidx;
			nodeidx = minNode(RR, nodeidx, *maxRNode);
			nodeRR = (RR + nodeidx);
			vidx = NODELEAST(*nodeRR);
		}
		if (lastnodeidx > *maxWNode)
			*maxWNode = lastnodeidx;
		*minRNode = minNode(R, *minRNode, *maxRNode);
		*maxRNode = maxNode(R, *maxRNode, *minRNode);

		nextInColor[heurg->n + (++size)] = sentinel;
	}

//	if (checkStackColor(R, W, size, "stackColoring")) {
//		printStackColor(size);
//		exit(0);
//	}

	return size;
}

/*!
 * \fn int mcsColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for vertex coloring, with vertex recoloring
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greates index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greates index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
int mcsColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);

	int size = stackColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);
//	printStackColor(size);
	if (lim == size && *minRNode <= *maxRNode)
		mcsRecolor(R, W, minRNode, maxRNode, minWNode, maxWNode, size);

	return size;
}

void mcsColoring_f(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode) {
	if (lim <= 1)
		greedyColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);
	else {
		int size = stackColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);
		if (*minRNode <= *maxRNode)
			mcsRecolor(R, W, minRNode, maxRNode, minWNode, maxWNode, size);
	}
}

/*!
 * \fn int fracColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode, int * maxRNode, int * minWNode, int * maxWNode)
 * \brief Greedy heuristic for fractional coloring.
 *
 * The vertices in the specified bitmap are colored, removed from this bitmap, and stored in another specified bitmap.
 * A maximum number of colors is specified. Vertices that cannot be colored with this number of colors remains in the input bitmap.
 *
 * The smallest and greatest indices of non-zero nodes of the specified bitmaps are updated.
 *
 * If \c R[\c *minRNode\c ] \c == \c 0, then an error may occur.
 *
 * \param R Input bitmap of vertices to color.
 * \param W Output bitmap to store vertices as soon as they are colored.
 * \param lim Maximum number of colors that can be used.
 * \param minRNode Smallest index of a non-zero node of the input bitmap.
 * \param maxRNode Greatest index of a non-zero node of the input bitmap.
 * \param minWNode Smallest index of a non-zero node of the output bitmap.
 * \param maxWNode Greatest index of a non-zero node of the output bitmap.
 *
 * \return The number of colors used.
 */
int fracColoring(NODETYPE * R, NODETYPE * W, int lim, int * minRNode,
		int * maxRNode, int * minWNode, int * maxWNode) {
	if (lim <= 2 || lim < heurg->maxcq - (heurg->maxcq >> 2))
		return greedyColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);

	int size = stackColoring(R, W, lim, minRNode, maxRNode, minWNode, maxWNode);

	if (lim >= 3 && size == lim) {
		int vidx;
		NODETYPE * nodeS;
		NODETYPE * nodeE;
		NODETYPE * nodeEE;
		int sentinel = heurg->n << 1;

		if (E == NULL) {
			int nnodes = NODEIDX(heurg->n-1) + 1;
			E = (NODETYPE *) calloc((nnodes << 1) + nnodes, WSIZE);
			EE = E + nnodes;
			S = EE + nnodes;
			memsz += (nnodes << (LOGW + 1)) + nnodes;
		} else {
			DELALL(EE + *minWNode, *maxWNode - *minWNode + 1);
			DELALL(S + *minWNode, *maxWNode - *minWNode + 1);
		}

		int tsz = 0, nsz = size;
		int k;

		int i, curColor;
		int minSNode;
		int maxSNode;
		int minENode, maxENode;

		for (k = 1;
				k == 1
						|| (nsz + tsz / k < tsz / (k - 1)
								|| -((double) nsz + tsz) / k
										+ ((double) tsz) / (k - 1) > 0.8);
				k++) {
			minSNode = *minWNode;
			maxSNode = *maxWNode;
			tsz += nsz;
			COPYALL(E+minSNode, EE+minSNode, maxSNode - minSNode + 1);
			for (curColor = 0; curColor < nsz - 1; curColor++) {
				for (i = nextInColor[heurg->n + curColor]; i < sentinel; i =
						nextInColor[i])
					S[NODEIDX(i)] = ADDTONODE(S[NODEIDX(i)], IDXINNODE(i));

				addAll(E, S, minSNode, maxSNode + 1);
				DELALL(EE + minSNode, maxSNode - minSNode + 1);
				for (i = nextInColor[heurg->n + curColor + 1]; i < sentinel; i =
						nextInColor[i])
					removeAll(E, NEIG(heurg, i), minSNode, maxSNode + 1);

				minENode = minNode(E, minSNode, maxSNode);
				maxENode = maxNode(E, maxSNode, minENode);
				nodeE = (E + minENode);
				vidx = NODELEAST(*nodeE);
				while (vidx >= 0) {
					int v = NELEM(minENode) + vidx;
					removeAll(E, NEIG(heurg, v), minENode, maxENode + 1);
					*nodeE = DELFROMNODE(*nodeE, vidx);
					nodeS = (S + minENode);
					*nodeS = DELFROMNODE(*nodeS, vidx);
					nodeEE = (EE + minENode);
					*nodeEE = ADDTONODE(*nodeEE, vidx);
					minENode = minNode(E, minENode, maxENode);
					nodeE = (E + minENode);
					vidx = NODELEAST(*nodeE);
				}
			}

			for (i = nextInColor[heurg->n + curColor]; i < sentinel; i =
					nextInColor[i])
				S[NODEIDX(i)] = ADDTONODE(S[NODEIDX(i)], IDXINNODE(i));
			minSNode = minNode(S, minSNode, maxSNode);
			maxSNode = maxNode(S, maxSNode, minSNode);
			nsz = stackColoring(S, E, lim, &minSNode, &maxSNode, &minENode,
					&maxENode);
		}
		if (k > 2)
			greedyColoring(R, W, size - (tsz / (k - 1)), minRNode, maxRNode,
					minWNode, maxWNode);
	}

	return size;
}
